package leetcode.top100;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @since 2019/12/28 0028 下午 12:17
 */
public class Code215_TopK {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        System.out.println(findKthLargest(nums, 2));

    }

    public static int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) return -1;
        return process3(nums, k);
    }

    //方式1：各种排序，时空复杂度取决于具体算法

    //方式2：partition或BFPRT，时间O(n),空间O(1)
    private static int process2(int[] nums, int k) {
        //总共n个数，第k大就是第 n - k + 1小，对应索引是n-k
//        return partition1(nums,nums.length-k);
        return partition2(nums, nums.length - k, 0, nums.length - 1);
    }

    //方式1：迭代版本，空间O(1)
    private static int partition1(int[] nums, int k) {
        int start = 0;
        int end = nums.length - 1;
        int[] range = doPartition(nums, start, end);
        while (range[0] > k || range[1] < k) {
            if (k > range[1]) start = range[1] + 1;
            if (k < range[0]) end = range[0] - 1;
            range = doPartition(nums, start, end);
        }
        return nums[k];
    }

    //2.2递归版本，空间最坏O(n)
    private static int partition2(int[] nums, int k, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        int[] range = doPartition(nums, start, end);
        if (range[0] <= k && range[1] >= k) {
            return nums[k];
        } else if (range[0] > k) {
            return partition2(nums, k, start, range[0] - 1);
        } else {
            return partition2(nums, k, range[1] + 1, end);
        }
    }


    private static int[] doPartition(int[] nums, int start, int end) {
        int target = nums[(int) (Math.random() * (end - start + 1)) + start];
        int less = start - 1;
        int more = end + 1;
        int cur = start;
        while (cur < more) {
            if (nums[cur] < target) {
                swap(nums, ++less, cur++);
            } else if (nums[cur] > target) {
                swap(nums, --more, cur);
            } else {
                cur++;
            }
        }
        return new int[]{less + 1, more - 1};
    }

    private static void swap(int[] nums, int i, int j) {
        if (i == j) return;
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }

    /**
     * 方式3：使用小根堆，一开始存储k个元素。堆顶是最小。
     * <p>
     * 然后拿数组中数据与堆顶比较，比堆顶大的则替代堆顶。
     * <p>
     * 时间O(nlogk), 空间O(k)
     */
    private static int process3(int[] nums, int k) {
        //默认小根堆
        Queue<Integer> minQueue = new PriorityQueue<>(k);
        for (int i = 0; i < nums.length; i++) {
            if (minQueue.size() < k) {
                minQueue.add(nums[i]);
            } else if (minQueue.peek() < nums[i]) {
                minQueue.poll();
                minQueue.add(nums[i]);
            }
        }
        return minQueue.peek();
    }
}
